package org.example.algorithm.sliding;

import java.util.ArrayDeque;
import java.util.Deque;

public class MaxSlidingWindowSolution {

    public static void main(String[] args) {
        int nums[] = {7,2,4};
        int k=2;
        MaxSlidingWindowSolution solution = new MaxSlidingWindowSolution();
        int[] res = solution.maxSlidingWindow(nums, k);
        for (int i=0;i<res.length;i++) {
            System.out.println(res[i]);
        }
    }

    //单调队列
    public int[] maxSlidingWindow(int[] nums, int k) {
        int[] ans = new int[nums.length-k+1];
        Deque<Integer> deque = new ArrayDeque<>();
        for (int i=0;i<nums.length;i++) {
            //入
            while (!deque.isEmpty() && nums[deque.getLast()]<=nums[i]) {
                deque.removeLast();
            }
            deque.addLast(i);
            //出
            if (i - deque.getFirst() >= k) {
                deque.removeFirst();
            }
            //记录答案
            if (i >= k-1) {
                ans[i-k+1] = nums[deque.getFirst()];
            }
        }
        return ans;
    }
}
